package linked_list;

/**
 * 翻转链表
 */
public class ReverseLinkedList {

    public static class Node {
        private int value;
        private Node next;

        public Node(int value) {
            this.value = value;
        }

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    public static class DoubleNode {
        private int value;
        private DoubleNode next;
        private DoubleNode last;

        public DoubleNode(int value) {
            this.value = value;
        }
    }

    /**
     * 删除链表中指定的值
     * 
     * @param head
     * @param num
     * @return
     */
    public static Node removeValue(Node head, int num) {

        return null;
    }

    /**
     * 反转链表
     * 
     * head
     * a -> b -> c -> null
     * a -> b -> a -> null
     * 
     * @param head
     * @return
     */
    public static Node reverseLinkedList(Node head) {
        Node pre = null;// 当前节点的前一个节点
        Node next = null;// 当前节点的下一个节点
        while (head != null) {// 当前节点不为null
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;

    }

    /**
     * 反转双向链表
     * 
     * @param head
     * @return
     */
    public static DoubleNode reverseDoubleList(DoubleNode head) {
        DoubleNode pre = null;
        DoubleNode next = null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            head.last = next;
            pre = head;
            head = next;
        }
        return pre;
    }

    public static void printNode(Node node) {
        while (node != null) {
            System.out.print(node.value + " ");
            node = node.next;
        }
        System.out.println();
    }

    public static void printDoubleNode(DoubleNode node) {
        while (node != null) {
            System.out.print(node.value + " ");
            node = node.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Node node5 = new Node(5, null);
        Node node4 = new Node(4, node5);
        Node node3 = new Node(3, node4);
        Node node2 = new Node(2, node3);
        Node node1 = new Node(1, node2);

        DoubleNode node51 = new DoubleNode(55);
        DoubleNode node42 = new DoubleNode(44);
        DoubleNode node33 = new DoubleNode(33);
        DoubleNode node24 = new DoubleNode(22);
        DoubleNode node15 = new DoubleNode(11);
        node15.next = node24;
        node15.last = null;
        node24.next = node33;
        node24.last = node15;
        node33.next = node42;
        node33.last = node24;
        node42.next = node51;
        node42.last = node33;

        printNode(node1);
        Node node11 = reverseLinkedList(node1);
        printNode(node11);

        printDoubleNode(node15);
        DoubleNode node12 = reverseDoubleList(node15);
        printDoubleNode(node12);
    }

}
